package com.yoshino.leetcode.improve40.twentyfifth;

import java.util.*;

class Solution {
    public int[][] merge2(int[][] intervals) {
        if (intervals.length == 0) {
            return new int[0][2];
        }
        // 合并：左边界按小到大，依次两两合并
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> mer = new ArrayList<>();
        for (int i = 0; i < intervals.length; i++) {
            int left = intervals[i][0], right = intervals[i][1];
            // 从数组中取出
            if (mer.isEmpty() || mer.get(mer.size() - 1)[1] < left) {
                // 不含任何数，左边界大于数组最小右边界
                mer.add(new int[]{left, right});
            } else {
                // 合并
                mer.get(mer.size() - 1)[1] = Math.max(mer.get(mer.size() - 1)[1], right);
            }
        }
        return mer.toArray(new int[mer.size()][]);
    }

    public int[][] merge(int[][] intervals) {
        if (intervals.length < 2) {
            return intervals;
        }
        // 合并：左边界按小到大，依次两两合并
        Arrays.sort(intervals, Comparator.comparingInt(a -> a[0]));
        List<int[]> mer = new ArrayList<>();
        int[] tmp = intervals[0];
        for (int i = 1; i < intervals.length; i++) {
            if (tmp[1] > intervals[i][0]) {
                // 合并
                tmp[1] = Math.max(tmp[1], intervals[i][1]);
            } else {
                mer.add(tmp);
                tmp = intervals[i];
            }
        }
        mer.add(tmp);
        return mer.toArray(new int[mer.size()][]);
    }

    public int[] relativeSortArray(int[] arr1, int[] arr2) {
        // arr2：用哈希存储下来相对位置
        // arr1：用哈希存储出现次数，数组存储未出现的
        Map<Integer, Integer> matchMap = new HashMap<>(), countMap = new HashMap<>();
        List<Integer> temp = new ArrayList<>();
        for (int i = 0; i < arr2.length; i++) {
            matchMap.put(arr2[i], i);
        }
        for (int i = 0; i < arr1.length; i++) {
            if (matchMap.containsKey(arr1[i])) {
                // 存在
                countMap.put(arr1[i], countMap.getOrDefault(arr1[i], 0) + 1);
            } else {
                temp.add(arr1[i]);
            }
        }
        int ind = 0;
        for (int i = 0; i < arr2.length; i++) {
            int k = countMap.getOrDefault(arr2[i], 0);
            while (k-- > 0) {
                arr1[ind++] = arr2[i];
            }
        }
        Collections.sort(temp);
        for (int i = 0; i < temp.size(); i++) {
            arr1[ind++] = temp.get(i);
        }
        return arr1;
    }
}